import java.sql.Array;
import java.sql.SQLOutput;
import java.util.*;

class Solution1 {
    List<List<Integer>> list;
    int n;
    boolean[] fn;
    public List<List<Integer>> permute(int[] nums) {
        list =new ArrayList<>();
        n=nums.length;
        fn=new boolean[n];
        List<Integer> ret=new ArrayList<Integer>();
        df(nums,ret);
        return list;

    }
    public void df(int[] nums,List<Integer> ret){

        if(ret.size()==n){
            list.add(new ArrayList<>(ret));
            return;
        }

        for(int i=0;i<n;i++){
            List<Integer> list1=new ArrayList<>(ret);
            if(!fn[i]){
                list1.add(nums[i]);
                fn[i]=true;
                df(nums,list1);
                fn[i]=false;;
            }

        }
    }
}
class Solution100{
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer,List<Integer>> hash=new HashMap<>();
        int n=prerequisites.length;
        int[] fn=new int[ numCourses];
        for(int i=0;i<n;i++){
            int a=prerequisites[i][0];int b=prerequisites[i][1];
            if(!hash.containsKey(b)){
                hash.put(b,new ArrayList<>());
            }
            List<Integer> A=hash.get(b);
            A.add(a);
            hash.put(b,A);
            fn[a]++;
        }
        Queue<Integer> q=new LinkedList<>();
        for(int i=0;i<n;i++){
            if(fn[i]==0) q.add(i);
        }
        while(!q.isEmpty()){
            int a= q.poll();
            List<Integer> A=hash.getOrDefault(a,new ArrayList<>());
            for(int x:A){
                fn[x]--;
                if(fn[x]==0) q.add(x);
            }
        }
        for(int i=0;i<n;i++){
            if(fn[i]>0) return false;
        }
        return true;
    }
}
class Solution101{
    public String longestPalindrome(String s) {
        String ret = "";
        for (int i = 1; i < s.length(); i++) {
            String ret1 = isChrild(s, i);

            String ret2 = isChrild1(s, i - 1, i);

            if (ret1.length() > ret.length())
                ret = ret1;
            if (ret2.length() > ret.length())
                ret = ret2;
        }
        return ret;

    }

    public String isChrild(String s, int i) {
        int begin = 0;
        int end = 0;
        int right = i + 1;
        int left = i - 1;
        while (right < s.length() && left >= 0) {
            if (s.charAt(left) == s.charAt(right)) {
                right++;
                left--;
            } else {
                break;
            }
        }
        begin = left + 1;
        end = right;
        return s.substring(begin, end);
    }

    public String isChrild1(String s, int left, int right) {
        int begin = 0;
        int end = 0;

        while (right < s.length() && left >= 0) {
            if (s.charAt(left) == s.charAt(right)) {
                right++;
                left--;
            } else {
                break;
            }
        }
        begin = left + 1;
        end = right;
        return s.substring(begin, end);
    }
}
public class Test {
    public static int longestPalindromeSubseq(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        int len=0;
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(i==j||i+1==j) dp[i][j]=j-i+1;
                    else dp[i][j]=dp[i+1][j-1]+2;
                    len=Math.max(len,dp[i][j]);
                }else{
                  dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

        return len;
    }
    public  static int minInsertions(String s) {
        int n=s.length();
        int[][] dp=new int[n][n];
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(i+1==j||i==j) dp[i][j]=0;
                    else dp[i][j]=dp[i+1][j-1];
                }
                else{
                    dp[i][j]=Math.min(dp[i][j-1],dp[i+1][j])+1;
                }
            }
        }
        return dp[0][n-1];
    }
    public static int longestCommonSubsequence(String text1, String text2) {
        Set<Character> hash=new HashSet<>();
        for(int i=0;i<text1.length();i++){
            hash.add(text1.charAt(i));
        }
        int count=0;
        for(int i=0;i<text2.length();i++){
            char ch=text2.charAt(i);
            if(hash.contains(ch)) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums={7,7,7,7,7,7};
        Map<Integer,List<Integer>> hash=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(!hash.containsKey(nums[i])){
                hash.put(nums[i],new ArrayList<Integer>());
            }
            hash.get((nums[i])).add(i);
        }
        int n=nums.length;
        int sum=0;
        int[][] dp=new int[n][n];
        for(int i=2;i<n;i++){
            for(int j=1;j<i;j++){
                int a=2*nums[j]-nums[i];
                if(hash.containsKey(a)){
                    for(int x:hash.get(a)){
                        if(x<j){
                            dp[j][i]=dp[j][i]+dp[x][j]+1;

                        }
                    }
                }
                sum+=dp[j][i];
            }

        }
        System.out.println(sum);

//
//       List<int[]> list=new ArrayList<>();
//       list.add(new int[]{1,2,3,4});
//       list.add(new int[]{1,2,4,1});
//
//        int[] arr={1,0,-2,4,5};
//        int n = arr.length;
//        int ret = 1;
//        int left = 0, right = 0;
//
//        while (right < n - 1) {
//            if (left == right) {
//                if (arr[left] == arr[left + 1]) {
//                    left++;
//                }
//                right++;
//            } else {
//                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
//                    right++;
//                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
//                    right++;
//                } else {
//                    left = right;
//                }
//            }
//            ret = Math.max(ret, right - left + 1);
//        }
//        System.out.println(ret);
    }
    public static void main1(String[] args) {
        int[] nums={3,30,34,5,9};
        int n=nums.length;
        Integer[] arr=new Integer[n];
        for(int i=0;i<n;i++){
            arr[i]=nums[i];
        }
       
        Arrays.sort(arr,(a,b)->{
            int x=a;
            int  y=b;
            while(x<10000){
                x*=10;
            }
            while(y<10000){
                y*=10;
            }
            return y-x;
        });
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<n;i++){
            sb.append(Integer.valueOf(arr[i]));
        }
        System.out.println(sb.toString());
//        PriorityQueue<Double> q=new PriorityQueue<Double>((a,b)-> (int) (b - a));
//        String s="ada";
//        String S1="acdda";
//       int a=longestCommonSubsequence(s,S1);
//        System.out.println(a);
    }
}
